package andcheckcollection;

import java.lang.annotation.ElementType;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * CheckCollection类包含用于处理集合操作的工具和结构
 */
public class CheckCollection{

    /**
     * Element类表示集合中的一个元素
     * @param <V> 元素的值类型
     */
    private static class Element<V>{
        private V value;

        public Element(V value){
            this.value = value;
        }
        public V getValue(){
            return value;
        }
        public void setValue(V value){
            this.value = value;
        }
    }

    /**
     * UnionFindSet类实现并查集数据结构
     * @param <V> 集合中元素的类型
     */
    public static class UnionFindSet<V> {
        public HashMap<V,Element<V>> elementMap;
        public HashMap<Element<V>,Element<V>> fatherMap;
        public HashMap<Element<V>,Integer> sizeMap;

        /**
         * 构造函数，初始化并查集
         * @param values 初始化并查集的元素列表
         */
        public UnionFindSet(List<V> values){
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            values.forEach((value)->{
                Element<V> element = new Element<>(value);
                elementMap.put(value,element);
                fatherMap.put(element,element);
                sizeMap.put(element,1);
            });
        }

        /**
         * 查找元素的根节点，并进行路径压缩
         * @param element 要查找根节点的元素
         * @return 元素的根节点
         */
        public Element<V> findFather(Element<V> element){
            Stack<Element<V>> stack = new Stack();
            while(element != fatherMap.get(element)){
                stack.push(element);
                element = fatherMap.get(element);
            }
            while(!stack.isEmpty()){
                fatherMap.put(stack.pop(),element);
            }
            return element;
        }

        /**
         * 合并两个集合
         * @param v1 第一个集合中的元素
         * @param v2 第二个集合中的元素
         */
        public void union(V v1,V v2){
            Element<V> element1 = elementMap.get(v1);
            Element<V> element2 = elementMap.get(v2);
            if(element1 == null || element2 == null){
                return;
            }
            Element<V> father1 = findFather(element1);
            Element<V> father2 = findFather(element2);
            if(father1 != father2){
                int size1 = sizeMap.get(father1);
                int size2 = sizeMap.get(father2);
                Element<V> big = size1 >= size2 ? father1 : father2;
                Element<V> small = big == father1 ? father2 : father1;
                fatherMap.put(small,big);
                sizeMap.put(big,size1+size2);
                sizeMap.remove(small);
            }
        }

        /**
         * 判断两个元素是否属于同一个集合
         * @param v1 第一个元素
         * @param v2 第二个元素
         * @return 如果两个元素属于同一个集合返回true，否则返回false
         */
        public boolean isSameSet(V v1, V v2){
            Element<V> element1 = elementMap.get(v1);
            Element<V> element2 = elementMap.get(v2);
            if(element1 == null || element2 == null){
                return false;
            }
            return findFather(element1) == findFather(element2);
        }
    }
}
